#pragma once

#include <iostream>
using namespace std;
#include <vector>


namespace my_std
{

	template <class T>
	struct HashNode
	{
		HashNode<T>* _next;
		T _data;

		HashNode(const T& data)
			:_next(nullptr)
			, _data(data)
		{}

	};

	template <class K, class T, class KofT>
	class Hash;

	template <class K, class T, class Ref, class Prt, class KofT>
	struct HashIterator
	{
		typedef HashIterator<K, T, Ref, Prt, KofT> Self;
		typedef HashNode<T> Node;
		typedef const Hash<K, T, KofT> Hashtable;
		typedef HashIterator<K, T, T&, T*, KofT> iterator;

		Node* _node;
		Hashtable* _ptr;
		HashIterator(Node* node, Hashtable* ptr)
			:_node(node)
			, _ptr(ptr)
		{}

		HashIterator(const iterator& it)
			:_node(it._node)
			, _ptr(it._ptr)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Prt operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			Node* cur = _node;

			if (cur)
			{
				if (cur->_next)
				{
					_node = cur->_next;
				}
				else
				{
					KofT kt;
					size_t sz = _ptr->_arr.size();
					size_t hashi = kt(cur->_data) % sz;
					size_t i = 0;
					if (++hashi < sz)
					{
						for (i = hashi; i < sz; i++)
						{
							cur = _ptr->_arr[i];
							if (cur)
							{
								_node = cur;
								return *this;
							}
						}
						hashi = i;
					}

					if (sz == hashi)
						_node = nullptr;

				}
			}

			return *this;

		}

		bool operator!=(const Self& it)const
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)const
		{
			return _node == it._node;
		}


	};


	template <class K, class T, class KofT>
	class Hash
	{
		template <class K, class T, class Ref, class Prt, class KofT>
		friend struct HashIterator;
	public:
		typedef HashIterator<K, T, T&, T*, KofT> iterator;
		typedef HashIterator<K, T, const T&, const T*, KofT> const_iterator;
		typedef HashNode<T> Node;

		iterator begin()
		{
			for (size_t i = 0; i < _arr.size(); i++)
			{
				Node* cur = _arr[i];
				if (cur)
				{
					return iterator(cur, this);
				}

			}
			return iterator(nullptr, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin()const
		{
			for (size_t i = 0; i < _arr.size(); i++)
			{
				Node* cur = _arr[i];
				if (cur)
				{
					return const_iterator(cur, this);
				}

			}
			return const_iterator(nullptr, this);
		}

		const_iterator end()const
		{
			return const_iterator(nullptr, this);
		}




		Hash()
			:_n(0)
		{
			_arr.resize(10);
		}

		Hash(const Hash& ha)
		{
			_n = ha._n;
			for (auto& v : ha._arr)
			{
				_arr.push_back(v);
			}
		}

		pair<iterator, bool> insert(const T& data)
		{
			KofT kt;
			pair<iterator, bool> fd = Find(kt(data));
			if (fd.second)
			{
				return make_pair(fd.first, false);
			}
			size_t hf = _n * 10 / _arr.size();
			if (hf > 7)
			{
				vector<Node*> v;
				v.resize(_arr.size() * 2, nullptr);
				for (size_t i = 0; i < _arr.size(); i++)
				{
					Node* cur = _arr[i];
					while (cur)
					{
						size_t hashj = kt(cur->_data) % v.size();
						Node* tmp = cur;
						tmp->_next = v[hashj];
						v[hashj] = tmp;

						cur = cur->_next;
					}

				}
				swap(_arr, v);
			}

			Node* newnode = new Node(data);
			size_t hashi = kt(data) % _arr.size();
			newnode->_next = _arr[hashi];
			_arr[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode, this), true);
		}

		pair<iterator, bool> Find(const K& key)
		{
			KofT kt;
			size_t hashi = key % _arr.size();
			Node* cur = _arr[hashi];
			while (cur)
			{
				if (kt(cur->_data) == key)
				{
					return make_pair(iterator(cur, this), true);
				}
				cur = cur->_next;
			}
			return make_pair(end(), false);
		}


		pair<iterator, bool> earse(const K& key)
		{
			KofT kt;
			size_t hashi = key % _arr.size();
			Node* cur = _arr[hashi];
			Node* prev = cur;
			while (cur)
			{
				if (kt(cur->_data) == key)
				{

					Node* next = cur->_next;

					if (!_arr[hashi]->_next)
					{
						_arr[hashi] = nullptr;
					}
					else
					{
						prev->_next = next;
					}
					delete cur;
					--_n;
					return make_pair(iterator(prev, this), true);
				}
				prev = cur;
				cur = cur->_next;
			}
			return make_pair(end(), false);
		}

	private:
		vector<Node*> _arr;
		size_t _n;

	};
}